﻿using System.Collections;
using System.Collections.Generic;
using System;

public class DesignQuestion  
{

}


/// <summary>
/// 155. 最小栈
/// 链接：https://leetcode-cn.com/problems/min-stack/
/// 方法一：辅助栈：主栈插入元素对应辅助栈对应最小值，插入和删除都要对应操作
/// 时间复杂度：O(1) 插入或者删除最大都是2次操作
/// 空间复杂度：O(N) 插入或者删除 最大都是N ，两个栈最大是2N
/// 
/// 变种思考：不能使用额外空间，思路是栈里保存差值
/// </summary>
public class MinStack
{
    Stack<int> minStack;
    Stack<int> curStack;
    int minValue;

    public MinStack()
    {
        minStack = new Stack<int>();
        curStack = new Stack<int>();
        minStack.Push(int.MaxValue); //先压入最大值
    }

    public void Push(int val)
    {
        curStack.Push(val);
        minStack.Push(Math.Min(val, minStack.Peek())); //压入最小值    
    }

    public void Pop() 
    {
        curStack.Pop();
        minStack.Pop(); 
    }

    public int Top()
    {
        return curStack.Peek();
    }

    public int GetMin()
    {
        return minStack.Peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.Push(val);
 * obj.Pop();
 * int param_3 = obj.Top();
 * int param_4 = obj.GetMin();
 */
